package main.LeetCode75.Level2;

import java.util.*;

public class Day11_Day15 {
    public static void main(String[] args) {
        System.out.println("**************************Day11**************************");
        System.out.println("Question210：课程表 II");
        System.out.println("Question815：公交路线");
        System.out.println("**************************Day12**************************");
        System.out.println("Question198：打家劫舍");
        System.out.println("Question322：零钱兑换");
        System.out.println("**************************Day13**************************");
        System.out.println("Question416：分割等和子集");
        System.out.println("Question152：乘积最大子数组");
        System.out.println("**************************Day14**************************");
        System.out.println("Question3：无重复字符的最长子串");
        System.out.println("Question16：最接近的三数之和");
        System.out.println("Question76：最小覆盖子串");
        System.out.println("**************************Day15**************************");
        System.out.println("Question100：相同的树");
        System.out.println("Question101：对称二叉树");
        System.out.println("Question199：二叉树的右视图");
    }
}

class Question210{
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Deque<Integer> queue=new LinkedList<>();
        int [] ins=new int [numCourses];//入度数
        int [] res=new int [numCourses];
        int cnt=0;//一个指针，表示res数组实际有的元素个数
        int n=prerequisites.length;
        for(int i=0;i<n;i++){
            ins[prerequisites[i][0]]++;
        }
        for(int i=0;i<numCourses;i++){//先找到没有入度的结点，入队
            if(ins[i]==0) queue.offer(i);
        }
        while(!queue.isEmpty()){
            int peek=queue.poll();//将队列中的队首元素出队
            res[cnt++]=peek;
            for(int []p:prerequisites){
                if(p[1]==peek){
                    ins[p[0]]--;
                    if(ins[p[0]]==0){
                        queue.offer(p[0]);
                    }
                }
            }
        }
        return cnt==numCourses ? res : new int [0];
    }
}

class Question815{
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source==target) return 0;
        int length= routes.length;
        boolean[][] edges=new boolean[length][length];
        Map<Integer,List<Integer>> map=new HashMap<>();
        for (int i=0;i<length;i++){//建立邻接矩阵
            for (int station:routes[i]){
                List<Integer> list=map.getOrDefault(station,new ArrayList<>());
                for (int j:list){
                    edges[i][j]=true;
                    edges[j][i]=true;
                }
                list.add(i);
                map.put(station,list);
            }
        }
        int[] dis=new int[length];
        Arrays.fill(dis,-1);
        Queue<Integer> queue=new LinkedList<>();
        for (int bus:map.getOrDefault(source,new ArrayList<>())){
            dis[bus]=1;
            queue.offer(bus);
        }
        while (!queue.isEmpty()){
            int x=queue.poll();
            for (int y=0;y<length;y++){
                if (edges[x][y]&&dis[y]==-1){
                    dis[y]=dis[x]+1;
                    queue.offer(y);
                }
            }
        }
        int ret = Integer.MAX_VALUE;
        for (int bus : map.getOrDefault(target, new ArrayList<Integer>())) {
            if (dis[bus] != -1) {
                ret = Math.min(ret, dis[bus]);
            }
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;
    }
}

class Question198{
    public int rob(int[] nums) {
        int length= nums.length,result=-1;
        int[] dp=new int[length];
        for (int i=0;i<length;i++){//最后偷第i家
            int max=0;
            if (i==0||i==1){//前两家自身
                dp[i]=nums[i];
                result=Math.max(result,dp[i]);
                continue;
            }
            for (int j=0;j<i-1;j++){//选取最后偷第i家情况的最优选择
                max=Math.max(max,dp[j]);
            }
            dp[i]=max+nums[i];
            result=Math.max(result,dp[i]);
        }
        return result;
    }
}

class Question322{
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        for (int j = 0; j < dp.length; j++) dp[j] = max;//0行
        dp[0] = 0;//0列
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j - coins[i]] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}

class Question416{
    public boolean canPartition(int[] nums) {
        int m=0;
        for (int num:nums) m+=num;
        if (m%2!=0) return false;
        m/=2;
        boolean[] dp=new boolean[m+1];
        dp[0]=true;
        for (int x:nums){
            for (int j=m;j>=x;j--){
                dp[j]|=dp[j-x];
            }
        }
        return dp[m];
    }
}

class Question152{
    public int maxProduct(int[] nums) {//动态规划表
        int max=Integer.MIN_VALUE;
        int[] dp=new int[nums.length];
        for (int i=0;i< nums.length;i++){
            dp[i]=nums[i];
            max=Math.max(max,dp[i]);
            for (int j=i+1;j< nums.length;j++){
                dp[j]=dp[j-1]*nums[j];
                max=Math.max(max,dp[j]);
            }
        }
        return max;
    }
}

class Question3{
    public int lengthOfLongestSubstring(String s) {
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

class Question16{
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int result = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length;i++) {
            int start = i+1, end = nums.length - 1;
            while(start < end) {
                int sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - result))
                    result = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return result;
            }
        }
        return result;
    }
}

class Question76{
    public boolean process(int[] curCount,int[] targetCount){
        for (int i=0;i< targetCount.length;i++){
            if (targetCount[i]!=0&&curCount[i]<targetCount[i]) return false;//目标字符数不足
        }
        return true;
    }
    public String minWindow(String s, String t) {
        int left=0,right=0,start=-1,minLength=Integer.MAX_VALUE;
        if (t.length()>s.length()) return "";
        int[] targetCount=new int[150],curCount=new int[150];
        char[] str=s.toCharArray();
        for (char c:t.toCharArray()) targetCount[c]++;
        while (right< str.length){
            curCount[str[right]]++;//右扩
            while (process(curCount,targetCount)&&left<=right){//左缩
                if (right-left+1<minLength){//满足更新
                    start=left;
                    minLength=right-left+1;
                }
                curCount[str[left]]--;
                left++;
            }
            right++;
        }
        if (start==-1) return "";
        else return s.substring(start,start+minLength);
    }
}

class Question100{
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

class Question101{
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

class Question199{
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null) return list;
        queue.add(root);
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i=0;i<size;i++){
                TreeNode curNode=queue.poll();
                if (i==size-1){//该层最右侧元素
                    list.add(curNode.val);
                }
                if (curNode.left!=null) queue.add(curNode.left);
                if (curNode.right!=null) queue.add(curNode.right);
            }
        }
        return list;
    }
}